<!DOCTYPE HTML>
<html lang="en" >
    
    <head>
        
        <meta charset="UTF-8">
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <title>算法效率衡量 | 数据结构与算法（Python）</title>
        <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
        <meta name="description" content="">
        <meta name="generator" content="GitBook 2.6.7">
        
        
        <meta name="HandheldFriendly" content="true"/>
        <meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no">
        <meta name="apple-mobile-web-app-capable" content="yes">
        <meta name="apple-mobile-web-app-status-bar-style" content="black">
        <link rel="apple-touch-icon-precomposed" sizes="152x152" href="../gitbook/images/apple-touch-icon-precomposed-152.png">
        <link rel="shortcut icon" href="../gitbook/images/favicon.ico" type="image/x-icon">
        
    <link rel="stylesheet" href="../gitbook/style.css">
    
        
        <link rel="stylesheet" href="../gitbook/plugins/gitbook-plugin-highlight/website.css">
        
    
        
        <link rel="stylesheet" href="../gitbook/plugins/gitbook-plugin-search/search.css">
        
    
        
        <link rel="stylesheet" href="../gitbook/plugins/gitbook-plugin-fontsettings/website.css">
        
    
    

        
    
    
    <link rel="next" href="../chapter1/section5.html" />
    
    
    <link rel="prev" href="../chapter1/section3.html" />
    

        
    </head>
    <body>
        
        
    <div class="book"
        data-level="1.4"
        data-chapter-title="算法效率衡量"
        data-filepath="chapter1/section4.md"
        data-basepath=".."
        data-revision="Fri Mar 31 2017 18:24:30 GMT+0800 (CST)"
        data-innerlanguage="">
    

<div class="book-summary">
    <nav role="navigation">
        <ul class="summary">
            
            
            
            

            

            
    
        <li class="chapter " data-level="0" data-path="index.html">
            
                
                    <a href="../index.html">
                
                        <i class="fa fa-check"></i>
                        
                        数据结构与算法（Python）
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="1" data-path="chapter1/index.html">
            
                
                    <a href="../chapter1/index.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>1.</b>
                        
                        引入概念
                    </a>
            
            
            <ul class="articles">
                
    
        <li class="chapter " data-level="1.1" data-path="chapter1/section1.html">
            
                
                    <a href="../chapter1/section1.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>1.1.</b>
                        
                        第一次尝试
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="1.2" data-path="chapter1/section2.html">
            
                
                    <a href="../chapter1/section2.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>1.2.</b>
                        
                        算法的提出
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="1.3" data-path="chapter1/section3.html">
            
                
                    <a href="../chapter1/section3.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>1.3.</b>
                        
                        第二次尝试
                    </a>
            
            
        </li>
    
        <li class="chapter active" data-level="1.4" data-path="chapter1/section4.html">
            
                
                    <a href="../chapter1/section4.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>1.4.</b>
                        
                        算法效率衡量
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="1.5" data-path="chapter1/section5.html">
            
                
                    <a href="../chapter1/section5.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>1.5.</b>
                        
                        算法分析
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="1.6" data-path="chapter1/section6.html">
            
                
                    <a href="../chapter1/section6.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>1.6.</b>
                        
                        常见时间复杂度
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="1.7" data-path="chapter1/section7.html">
            
                
                    <a href="../chapter1/section7.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>1.7.</b>
                        
                        Python内置类型性能分析
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="1.8" data-path="chapter1/section8.html">
            
                
                    <a href="../chapter1/section8.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>1.8.</b>
                        
                        数据结构
                    </a>
            
            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="2" data-path="chapter2/index.html">
            
                
                    <a href="../chapter2/index.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>2.</b>
                        
                        顺序表
                    </a>
            
            
            <ul class="articles">
                
    
        <li class="chapter " data-level="2.1" data-path="chapter2/section1.html">
            
                
                    <a href="../chapter2/section1.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>2.1.</b>
                        
                        顺序表的形式
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="2.2" data-path="chapter2/section2.html">
            
                
                    <a href="../chapter2/section2.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>2.2.</b>
                        
                        顺序表的结构与实现
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="2.3" data-path="chapter2/section3.html">
            
                
                    <a href="../chapter2/section3.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>2.3.</b>
                        
                        顺序表的操作
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="2.4" data-path="chapter2/section4.html">
            
                
                    <a href="../chapter2/section4.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>2.4.</b>
                        
                        Python中的顺序表
                    </a>
            
            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="3" data-path="chapter3/index.html">
            
                
                    <a href="../chapter3/index.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>3.</b>
                        
                        链表
                    </a>
            
            
            <ul class="articles">
                
    
        <li class="chapter " data-level="3.1" data-path="chapter3/section1.html">
            
                
                    <a href="../chapter3/section1.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>3.1.</b>
                        
                        单向链表
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="3.2" data-path="chapter3/section2.html">
            
                
                    <a href="../chapter3/section2.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>3.2.</b>
                        
                        单项循环链表
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="3.3" data-path="chapter3/section3.html">
            
                
                    <a href="../chapter3/section3.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>3.3.</b>
                        
                        双向链表
                    </a>
            
            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="4" data-path="chapter4/index.html">
            
                
                    <a href="../chapter4/index.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>4.</b>
                        
                        栈
                    </a>
            
            
            <ul class="articles">
                
    
        <li class="chapter " data-level="4.1" data-path="chapter4/section1.html">
            
                
                    <a href="../chapter4/section1.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>4.1.</b>
                        
                        栈结构实现
                    </a>
            
            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="5" data-path="chapter5/index.html">
            
                
                    <a href="../chapter5/index.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>5.</b>
                        
                        队列
                    </a>
            
            
            <ul class="articles">
                
    
        <li class="chapter " data-level="5.1" data-path="chapter5/section1.html">
            
                
                    <a href="../chapter5/section1.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>5.1.</b>
                        
                        队列的实现
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="5.2" data-path="chapter5/section3.html">
            
                
                    <a href="../chapter5/section3.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>5.2.</b>
                        
                        双端队列
                    </a>
            
            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="6" data-path="chapter6/index.html">
            
                
                    <a href="../chapter6/index.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>6.</b>
                        
                        排序与搜索
                    </a>
            
            
            <ul class="articles">
                
    
        <li class="chapter " data-level="6.1" data-path="chapter6/section1.html">
            
                
                    <a href="../chapter6/section1.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>6.1.</b>
                        
                        冒泡排序
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="6.2" data-path="chapter6/section2.html">
            
                
                    <a href="../chapter6/section2.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>6.2.</b>
                        
                        选择排序
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="6.3" data-path="chapter6/section3.html">
            
                
                    <a href="../chapter6/section3.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>6.3.</b>
                        
                        插入排序
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="6.4" data-path="chapter6/section4.html">
            
                
                    <a href="../chapter6/section4.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>6.4.</b>
                        
                        快速排序
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="6.5" data-path="chapter6/section5.html">
            
                
                    <a href="../chapter6/section5.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>6.5.</b>
                        
                        希尔排序
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="6.6" data-path="chapter6/section6.html">
            
                
                    <a href="../chapter6/section6.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>6.6.</b>
                        
                        归并排序
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="6.7" data-path="chapter6/section7.html">
            
                
                    <a href="../chapter6/section7.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>6.7.</b>
                        
                        常见排序算法效率比较
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="6.8" data-path="chapter6/section8.html">
            
                
                    <a href="../chapter6/section8.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>6.8.</b>
                        
                        搜索
                    </a>
            
            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="7" data-path="chapter7/index.html">
            
                
                    <a href="../chapter7/index.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>7.</b>
                        
                        树与树算法
                    </a>
            
            
            <ul class="articles">
                
    
        <li class="chapter " data-level="7.1" data-path="chapter7/section1.html">
            
                
                    <a href="../chapter7/section1.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>7.1.</b>
                        
                        二叉树
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="7.2" data-path="chapter7/section2.html">
            
                
                    <a href="../chapter7/section2.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>7.2.</b>
                        
                        二叉树的遍历
                    </a>
            
            
        </li>
    

            </ul>
            
        </li>
    


            
            <li class="divider"></li>
            <li>
                <a href="https://www.gitbook.com" target="blank" class="gitbook-link">
                    Published with GitBook
                </a>
            </li>
            
        </ul>
    </nav>
</div>

    <div class="book-body">
        <div class="body-inner">
            <div class="book-header" role="navigation">
    <!-- Actions Left -->
    

    <!-- Title -->
    <h1>
        <i class="fa fa-circle-o-notch fa-spin"></i>
        <a href="../" >数据结构与算法（Python）</a>
    </h1>
</div>

            <div class="page-wrapper" tabindex="-1" role="main">
                <div class="page-inner">
                
                
                    <section class="normal" id="section-">
                    
                        <h1 id="&#x7B97;&#x6CD5;&#x6548;&#x7387;&#x8861;&#x91CF;">&#x7B97;&#x6CD5;&#x6548;&#x7387;&#x8861;&#x91CF;</h1>
<h2 id="&#x6267;&#x884C;&#x65F6;&#x95F4;&#x53CD;&#x5E94;&#x7B97;&#x6CD5;&#x6548;&#x7387;">&#x6267;&#x884C;&#x65F6;&#x95F4;&#x53CD;&#x5E94;&#x7B97;&#x6CD5;&#x6548;&#x7387;</h2>
<p>&#x5BF9;&#x4E8E;&#x540C;&#x4E00;&#x95EE;&#x9898;&#xFF0C;&#x6211;&#x4EEC;&#x7ED9;&#x51FA;&#x4E86;&#x4E24;&#x79CD;&#x89E3;&#x51B3;&#x7B97;&#x6CD5;&#xFF0C;&#x5728;&#x4E24;&#x79CD;&#x7B97;&#x6CD5;&#x7684;&#x5B9E;&#x73B0;&#x4E2D;&#xFF0C;&#x6211;&#x4EEC;&#x5BF9;&#x7A0B;&#x5E8F;&#x6267;&#x884C;&#x7684;&#x65F6;&#x95F4;&#x8FDB;&#x884C;&#x4E86;&#x6D4B;&#x7B97;&#xFF0C;&#x53D1;&#x73B0;&#x4E24;&#x6BB5;&#x7A0B;&#x5E8F;&#x6267;&#x884C;&#x7684;&#x65F6;&#x95F4;&#x76F8;&#x5DEE;&#x60AC;&#x6B8A;&#xFF08;214.583347&#x79D2;&#x76F8;&#x6BD4;&#x4E8E;0.182897&#x79D2;&#xFF09;&#xFF0C;&#x7531;&#x6B64;&#x6211;&#x4EEC;&#x53EF;&#x4EE5;&#x5F97;&#x51FA;&#x7ED3;&#x8BBA;&#xFF1A;<strong>&#x5B9E;&#x73B0;&#x7B97;&#x6CD5;&#x7A0B;&#x5E8F;&#x7684;&#x6267;&#x884C;&#x65F6;&#x95F4;&#x53EF;&#x4EE5;&#x53CD;&#x5E94;&#x51FA;&#x7B97;&#x6CD5;&#x7684;&#x6548;&#x7387;&#xFF0C;&#x5373;&#x7B97;&#x6CD5;&#x7684;&#x4F18;&#x52A3;&#x3002;</strong></p>
<h2 id="&#x5355;&#x9760;&#x65F6;&#x95F4;&#x503C;&#x7EDD;&#x5BF9;&#x53EF;&#x4FE1;&#x5417;&#xFF1F;">&#x5355;&#x9760;&#x65F6;&#x95F4;&#x503C;&#x7EDD;&#x5BF9;&#x53EF;&#x4FE1;&#x5417;&#xFF1F;</h2>
<p>&#x5047;&#x8BBE;&#x6211;&#x4EEC;&#x5C06;&#x7B2C;&#x4E8C;&#x6B21;&#x5C1D;&#x8BD5;&#x7684;&#x7B97;&#x6CD5;&#x7A0B;&#x5E8F;&#x8FD0;&#x884C;&#x5728;&#x4E00;&#x53F0;&#x914D;&#x7F6E;&#x53E4;&#x8001;&#x6027;&#x80FD;&#x4F4E;&#x4E0B;&#x7684;&#x8BA1;&#x7B97;&#x673A;&#x4E2D;&#xFF0C;&#x60C5;&#x51B5;&#x4F1A;&#x5982;&#x4F55;&#xFF1F;&#x5F88;&#x53EF;&#x80FD;&#x8FD0;&#x884C;&#x7684;&#x65F6;&#x95F4;&#x5E76;&#x4E0D;&#x4F1A;&#x6BD4;&#x5728;&#x6211;&#x4EEC;&#x7684;&#x7535;&#x8111;&#x4E2D;&#x8FD0;&#x884C;&#x7B97;&#x6CD5;&#x4E00;&#x7684;214.583347&#x79D2;&#x5FEB;&#x591A;&#x5C11;&#x3002;</p>
<p><strong>&#x5355;&#x7EAF;&#x4F9D;&#x9760;&#x8FD0;&#x884C;&#x7684;&#x65F6;&#x95F4;&#x6765;&#x6BD4;&#x8F83;&#x7B97;&#x6CD5;&#x7684;&#x4F18;&#x52A3;&#x5E76;&#x4E0D;&#x4E00;&#x5B9A;&#x662F;&#x5BA2;&#x89C2;&#x51C6;&#x786E;&#x7684;&#xFF01;</strong></p>
<p>&#x7A0B;&#x5E8F;&#x7684;&#x8FD0;&#x884C;&#x79BB;&#x4E0D;&#x5F00;&#x8BA1;&#x7B97;&#x673A;&#x73AF;&#x5883;&#xFF08;&#x5305;&#x62EC;&#x786C;&#x4EF6;&#x548C;&#x64CD;&#x4F5C;&#x7CFB;&#x7EDF;&#xFF09;&#xFF0C;&#x8FD9;&#x4E9B;&#x5BA2;&#x89C2;&#x539F;&#x56E0;&#x4F1A;&#x5F71;&#x54CD;&#x7A0B;&#x5E8F;&#x8FD0;&#x884C;&#x7684;&#x901F;&#x5EA6;&#x5E76;&#x53CD;&#x5E94;&#x5728;&#x7A0B;&#x5E8F;&#x7684;&#x6267;&#x884C;&#x65F6;&#x95F4;&#x4E0A;&#x3002;&#x90A3;&#x4E48;&#x5982;&#x4F55;&#x624D;&#x80FD;&#x5BA2;&#x89C2;&#x7684;&#x8BC4;&#x5224;&#x4E00;&#x4E2A;&#x7B97;&#x6CD5;&#x7684;&#x4F18;&#x52A3;&#x5462;&#xFF1F;</p>
<h2 id="&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x4E0E;&#x5927;o&#x8BB0;&#x6CD5;">&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x4E0E;&#x201C;&#x5927;O&#x8BB0;&#x6CD5;&#x201D;</h2>
<p>&#x6211;&#x4EEC;&#x5047;&#x5B9A;&#x8BA1;&#x7B97;&#x673A;&#x6267;&#x884C;&#x7B97;&#x6CD5;&#x6BCF;&#x4E00;&#x4E2A;&#x57FA;&#x672C;&#x64CD;&#x4F5C;&#x7684;&#x65F6;&#x95F4;&#x662F;&#x56FA;&#x5B9A;&#x7684;&#x4E00;&#x4E2A;&#x65F6;&#x95F4;&#x5355;&#x4F4D;&#xFF0C;&#x90A3;&#x4E48;&#x6709;&#x591A;&#x5C11;&#x4E2A;&#x57FA;&#x672C;&#x64CD;&#x4F5C;&#x5C31;&#x4EE3;&#x8868;&#x4F1A;&#x82B1;&#x8D39;&#x591A;&#x5C11;&#x65F6;&#x95F4;&#x5355;&#x4F4D;&#x3002;&#x7B97;&#x7136;&#x5BF9;&#x4E8E;&#x4E0D;&#x540C;&#x7684;&#x673A;&#x5668;&#x73AF;&#x5883;&#x800C;&#x8A00;&#xFF0C;&#x786E;&#x5207;&#x7684;&#x5355;&#x4F4D;&#x65F6;&#x95F4;&#x662F;&#x4E0D;&#x540C;&#x7684;&#xFF0C;&#x4F46;&#x662F;&#x5BF9;&#x4E8E;&#x7B97;&#x6CD5;&#x8FDB;&#x884C;&#x591A;&#x5C11;&#x4E2A;&#x57FA;&#x672C;&#x64CD;&#x4F5C;&#xFF08;&#x5373;&#x82B1;&#x8D39;&#x591A;&#x5C11;&#x65F6;&#x95F4;&#x5355;&#x4F4D;&#xFF09;&#x5728;&#x89C4;&#x6A21;&#x6570;&#x91CF;&#x7EA7;&#x4E0A;&#x5374;&#x662F;&#x76F8;&#x540C;&#x7684;&#xFF0C;&#x7531;&#x6B64;&#x53EF;&#x4EE5;&#x5FFD;&#x7565;&#x673A;&#x5668;&#x73AF;&#x5883;&#x7684;&#x5F71;&#x54CD;&#x800C;&#x5BA2;&#x89C2;&#x7684;&#x53CD;&#x5E94;&#x7B97;&#x6CD5;&#x7684;&#x65F6;&#x95F4;&#x6548;&#x7387;&#x3002;</p>
<p>&#x5BF9;&#x4E8E;&#x7B97;&#x6CD5;&#x7684;&#x65F6;&#x95F4;&#x6548;&#x7387;&#xFF0C;&#x6211;&#x4EEC;&#x53EF;&#x4EE5;&#x7528;&#x201C;&#x5927;O&#x8BB0;&#x6CD5;&#x201D;&#x6765;&#x8868;&#x793A;&#x3002;</p>
<p><strong>&#x201C;&#x5927;O&#x8BB0;&#x6CD5;&#x201D;&#xFF1A;&#x5BF9;&#x4E8E;&#x5355;&#x8C03;&#x7684;&#x6574;&#x6570;&#x51FD;&#x6570;f&#xFF0C;&#x5982;&#x679C;&#x5B58;&#x5728;&#x4E00;&#x4E2A;&#x6574;&#x6570;&#x51FD;&#x6570;g&#x548C;&#x5B9E;&#x5E38;&#x6570;c&gt;0&#xFF0C;&#x4F7F;&#x5F97;&#x5BF9;&#x4E8E;&#x5145;&#x5206;&#x5927;&#x7684;n&#x603B;&#x6709;f(n)&lt;=c*g(n)&#xFF0C;&#x5C31;&#x8BF4;&#x51FD;&#x6570;g&#x662F;f&#x7684;&#x4E00;&#x4E2A;&#x6E10;&#x8FD1;&#x51FD;&#x6570;&#xFF08;&#x5FFD;&#x7565;&#x5E38;&#x6570;&#xFF09;&#xFF0C;&#x8BB0;&#x4E3A;f(n)=O(g(n))&#x3002;&#x4E5F;&#x5C31;&#x662F;&#x8BF4;&#xFF0C;&#x5728;&#x8D8B;&#x5411;&#x65E0;&#x7A77;&#x7684;&#x6781;&#x9650;&#x610F;&#x4E49;&#x4E0B;&#xFF0C;&#x51FD;&#x6570;f&#x7684;&#x589E;&#x957F;&#x901F;&#x5EA6;&#x53D7;&#x5230;&#x51FD;&#x6570;g&#x7684;&#x7EA6;&#x675F;&#xFF0C;&#x4EA6;&#x5373;&#x51FD;&#x6570;f&#x4E0E;&#x51FD;&#x6570;g&#x7684;&#x7279;&#x5F81;&#x76F8;&#x4F3C;&#x3002;</strong></p>
<p><strong>&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#xFF1A;&#x5047;&#x8BBE;&#x5B58;&#x5728;&#x51FD;&#x6570;g&#xFF0C;&#x4F7F;&#x5F97;&#x7B97;&#x6CD5;A&#x5904;&#x7406;&#x89C4;&#x6A21;&#x4E3A;n&#x7684;&#x95EE;&#x9898;&#x793A;&#x4F8B;&#x6240;&#x7528;&#x65F6;&#x95F4;&#x4E3A;T(n)=O(g(n))&#xFF0C;&#x5219;&#x79F0;O(g(n))&#x4E3A;&#x7B97;&#x6CD5;A&#x7684;&#x6E10;&#x8FD1;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#xFF0C;&#x7B80;&#x79F0;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#xFF0C;&#x8BB0;&#x4E3A;T(n)</strong></p>
<h2 id="&#x5982;&#x4F55;&#x7406;&#x89E3;&#x5927;o&#x8BB0;&#x6CD5;">&#x5982;&#x4F55;&#x7406;&#x89E3;&#x201C;&#x5927;O&#x8BB0;&#x6CD5;&#x201D;</h2>
<p>&#x5BF9;&#x4E8E;&#x7B97;&#x6CD5;&#x8FDB;&#x884C;&#x7279;&#x522B;&#x5177;&#x4F53;&#x7684;&#x7EC6;&#x81F4;&#x5206;&#x6790;&#x867D;&#x7136;&#x5F88;&#x597D;&#xFF0C;&#x4F46;&#x5728;&#x5B9E;&#x8DF5;&#x4E2D;&#x7684;&#x5B9E;&#x9645;&#x4EF7;&#x503C;&#x6709;&#x9650;&#x3002;&#x5BF9;&#x4E8E;&#x7B97;&#x6CD5;&#x7684;&#x65F6;&#x95F4;&#x6027;&#x8D28;&#x548C;&#x7A7A;&#x95F4;&#x6027;&#x8D28;&#xFF0C;&#x6700;&#x91CD;&#x8981;&#x7684;&#x662F;&#x5176;&#x6570;&#x91CF;&#x7EA7;&#x548C;&#x8D8B;&#x52BF;&#xFF0C;&#x8FD9;&#x4E9B;&#x662F;&#x5206;&#x6790;&#x7B97;&#x6CD5;&#x6548;&#x7387;&#x7684;&#x4E3B;&#x8981;&#x90E8;&#x5206;&#x3002;&#x800C;&#x8BA1;&#x91CF;&#x7B97;&#x6CD5;&#x57FA;&#x672C;&#x64CD;&#x4F5C;&#x6570;&#x91CF;&#x7684;&#x89C4;&#x6A21;&#x51FD;&#x6570;&#x4E2D;&#x90A3;&#x4E9B;&#x5E38;&#x91CF;&#x56E0;&#x5B50;&#x53EF;&#x4EE5;&#x5FFD;&#x7565;&#x4E0D;&#x8BA1;&#x3002;&#x4F8B;&#x5982;&#xFF0C;&#x53EF;&#x4EE5;&#x8BA4;&#x4E3A;3n<sup>2</sup>&#x548C;100n<sup>2</sup>&#x5C5E;&#x4E8E;&#x540C;&#x4E00;&#x4E2A;&#x91CF;&#x7EA7;&#xFF0C;&#x5982;&#x679C;&#x4E24;&#x4E2A;&#x7B97;&#x6CD5;&#x5904;&#x7406;&#x540C;&#x6837;&#x89C4;&#x6A21;&#x5B9E;&#x4F8B;&#x7684;&#x4EE3;&#x4EF7;&#x5206;&#x522B;&#x4E3A;&#x8FD9;&#x4E24;&#x4E2A;&#x51FD;&#x6570;&#xFF0C;&#x5C31;&#x8BA4;&#x4E3A;&#x5B83;&#x4EEC;&#x7684;&#x6548;&#x7387;&#x201C;&#x5DEE;&#x4E0D;&#x591A;&#x201D;&#xFF0C;&#x90FD;&#x4E3A;n<sup>2</sup>&#x7EA7;&#x3002;</p>
<h2 id="&#x6700;&#x574F;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;">&#x6700;&#x574F;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;</h2>
<p>&#x5206;&#x6790;&#x7B97;&#x6CD5;&#x65F6;&#xFF0C;&#x5B58;&#x5728;&#x51E0;&#x79CD;&#x53EF;&#x80FD;&#x7684;&#x8003;&#x8651;&#xFF1A;</p>
<ul>
<li>&#x7B97;&#x6CD5;&#x5B8C;&#x6210;&#x5DE5;&#x4F5C;&#x6700;&#x5C11;&#x9700;&#x8981;&#x591A;&#x5C11;&#x57FA;&#x672C;&#x64CD;&#x4F5C;&#xFF0C;&#x5373;<strong>&#x6700;&#x4F18;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;</strong></li>
<li>&#x7B97;&#x6CD5;&#x5B8C;&#x6210;&#x5DE5;&#x4F5C;&#x6700;&#x591A;&#x9700;&#x8981;&#x591A;&#x5C11;&#x57FA;&#x672C;&#x64CD;&#x4F5C;&#xFF0C;&#x5373;<strong>&#x6700;&#x574F;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;</strong></li>
<li>&#x7B97;&#x6CD5;&#x5B8C;&#x6210;&#x5DE5;&#x4F5C;&#x5E73;&#x5747;&#x9700;&#x8981;&#x591A;&#x5C11;&#x57FA;&#x672C;&#x64CD;&#x4F5C;&#xFF0C;&#x5373;<strong>&#x5E73;&#x5747;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;</strong></li>
</ul>
<p>&#x5BF9;&#x4E8E;&#x6700;&#x4F18;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#xFF0C;&#x5176;&#x4EF7;&#x503C;&#x4E0D;&#x5927;&#xFF0C;&#x56E0;&#x4E3A;&#x5B83;&#x6CA1;&#x6709;&#x63D0;&#x4F9B;&#x4EC0;&#x4E48;&#x6709;&#x7528;&#x4FE1;&#x606F;&#xFF0C;&#x5176;&#x53CD;&#x6620;&#x7684;&#x53EA;&#x662F;&#x6700;&#x4E50;&#x89C2;&#x6700;&#x7406;&#x60F3;&#x7684;&#x60C5;&#x51B5;&#xFF0C;&#x6CA1;&#x6709;&#x53C2;&#x8003;&#x4EF7;&#x503C;&#x3002;</p>
<p>&#x5BF9;&#x4E8E;&#x6700;&#x574F;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#xFF0C;&#x63D0;&#x4F9B;&#x4E86;&#x4E00;&#x79CD;&#x4FDD;&#x8BC1;&#xFF0C;&#x8868;&#x660E;&#x7B97;&#x6CD5;&#x5728;&#x6B64;&#x79CD;&#x7A0B;&#x5EA6;&#x7684;&#x57FA;&#x672C;&#x64CD;&#x4F5C;&#x4E2D;&#x4E00;&#x5B9A;&#x80FD;&#x5B8C;&#x6210;&#x5DE5;&#x4F5C;&#x3002;</p>
<p>&#x5BF9;&#x4E8E;&#x5E73;&#x5747;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#xFF0C;&#x662F;&#x5BF9;&#x7B97;&#x6CD5;&#x7684;&#x4E00;&#x4E2A;&#x5168;&#x9762;&#x8BC4;&#x4EF7;&#xFF0C;&#x56E0;&#x6B64;&#x5B83;&#x5B8C;&#x6574;&#x5168;&#x9762;&#x7684;&#x53CD;&#x6620;&#x4E86;&#x8FD9;&#x4E2A;&#x7B97;&#x6CD5;&#x7684;&#x6027;&#x8D28;&#x3002;&#x4F46;&#x53E6;&#x4E00;&#x65B9;&#x9762;&#xFF0C;&#x8FD9;&#x79CD;&#x8861;&#x91CF;&#x5E76;&#x6CA1;&#x6709;&#x4FDD;&#x8BC1;&#xFF0C;&#x4E0D;&#x662F;&#x6BCF;&#x4E2A;&#x8BA1;&#x7B97;&#x90FD;&#x80FD;&#x5728;&#x8FD9;&#x4E2A;&#x57FA;&#x672C;&#x64CD;&#x4F5C;&#x5185;&#x5B8C;&#x6210;&#x3002;&#x800C;&#x4E14;&#xFF0C;&#x5BF9;&#x4E8E;&#x5E73;&#x5747;&#x60C5;&#x51B5;&#x7684;&#x8BA1;&#x7B97;&#xFF0C;&#x4E5F;&#x4F1A;&#x56E0;&#x4E3A;&#x5E94;&#x7528;&#x7B97;&#x6CD5;&#x7684;&#x5B9E;&#x4F8B;&#x5206;&#x5E03;&#x53EF;&#x80FD;&#x5E76;&#x4E0D;&#x5747;&#x5300;&#x800C;&#x96BE;&#x4EE5;&#x8BA1;&#x7B97;&#x3002;</p>
<p><strong>&#x56E0;&#x6B64;&#xFF0C;&#x6211;&#x4EEC;&#x4E3B;&#x8981;&#x5173;&#x6CE8;&#x7B97;&#x6CD5;&#x7684;&#x6700;&#x574F;&#x60C5;&#x51B5;&#xFF0C;&#x4EA6;&#x5373;&#x6700;&#x574F;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x3002;</strong></p>
<h2 id="&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x7684;&#x51E0;&#x6761;&#x57FA;&#x672C;&#x8BA1;&#x7B97;&#x89C4;&#x5219;">&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x7684;&#x51E0;&#x6761;&#x57FA;&#x672C;&#x8BA1;&#x7B97;&#x89C4;&#x5219;</h2>
<ol>
<li>&#x57FA;&#x672C;&#x64CD;&#x4F5C;&#xFF0C;&#x5373;&#x53EA;&#x6709;&#x5E38;&#x6570;&#x9879;&#xFF0C;&#x8BA4;&#x4E3A;&#x5176;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x4E3A;O(1)</li>
<li>&#x987A;&#x5E8F;&#x7ED3;&#x6784;&#xFF0C;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x6309;<strong>&#x52A0;&#x6CD5;</strong>&#x8FDB;&#x884C;&#x8BA1;&#x7B97;</li>
<li>&#x5FAA;&#x73AF;&#x7ED3;&#x6784;&#xFF0C;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x6309;<strong>&#x4E58;&#x6CD5;</strong>&#x8FDB;&#x884C;&#x8BA1;&#x7B97;</li>
<li>&#x5206;&#x652F;&#x7ED3;&#x6784;&#xFF0C;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;<strong>&#x53D6;&#x6700;&#x5927;&#x503C;</strong></li>
<li>&#x5224;&#x65AD;&#x4E00;&#x4E2A;&#x7B97;&#x6CD5;&#x7684;&#x6548;&#x7387;&#x65F6;&#xFF0C;&#x5F80;&#x5F80;&#x53EA;&#x9700;&#x8981;&#x5173;&#x6CE8;&#x64CD;&#x4F5C;&#x6570;&#x91CF;&#x7684;&#x6700;&#x9AD8;&#x6B21;&#x9879;&#xFF0C;&#x5176;&#x5B83;&#x6B21;&#x8981;&#x9879;&#x548C;&#x5E38;&#x6570;&#x9879;&#x53EF;&#x4EE5;&#x5FFD;&#x7565;</li>
<li>&#x5728;&#x6CA1;&#x6709;&#x7279;&#x6B8A;&#x8BF4;&#x660E;&#x65F6;&#xFF0C;&#x6211;&#x4EEC;&#x6240;&#x5206;&#x6790;&#x7684;&#x7B97;&#x6CD5;&#x7684;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x90FD;&#x662F;&#x6307;<strong>&#x6700;&#x574F;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;</strong></li>
</ol>

                    
                    </section>
                
                
                </div>
            </div>
        </div>

        
        <a href="../chapter1/section3.html" class="navigation navigation-prev " aria-label="Previous page: 第二次尝试"><i class="fa fa-angle-left"></i></a>
        
        
        <a href="../chapter1/section5.html" class="navigation navigation-next " aria-label="Next page: 算法分析"><i class="fa fa-angle-right"></i></a>
        
    </div>
</div>

        
<script src="../gitbook/app.js"></script>

    
    <script src="../gitbook/plugins/gitbook-plugin-search/lunr.min.js"></script>
    

    
    <script src="../gitbook/plugins/gitbook-plugin-search/search.js"></script>
    

    
    <script src="../gitbook/plugins/gitbook-plugin-sharing/buttons.js"></script>
    

    
    <script src="../gitbook/plugins/gitbook-plugin-fontsettings/buttons.js"></script>
    

<script>
require(["gitbook"], function(gitbook) {
    var config = {"highlight":{},"search":{"maxIndexSize":1000000},"sharing":{"facebook":true,"twitter":true,"google":false,"weibo":false,"instapaper":false,"vk":false,"all":["facebook","google","twitter","weibo","instapaper"]},"fontsettings":{"theme":"white","family":"sans","size":2}};
    gitbook.start(config);
});
</script>

        
    </body>
    
</html>
